package exercises.leetcode;

import exercises.newcoder.util.TreeNode;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * <a href="https://leetcode-cn.com/problems/path-sum-iii/">
 * 437. 路径总和 III</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 * <p>
 * 示例 1：
 * <p>
 * 输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
 * 输出：3
 * 解释：和等于 8 的路径有 3 条，如图所示。
 * <p>
 * 示例 2：
 * <p>
 * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 * 输出：3
 *  
 * <p>
 * 提示:
 * <li>二叉树的节点个数的范围是 [0,1000]</li>
 * <li>-109 <= Node.val <= 109 </li>
 * <li>-1000 <= targetSum <= 1000 </li>
 *
 * @author or2
 * @date 2021年09月28日 时间: 14:06
 */
public class No437 {
    private int res = 0;
    private int sum = 0;
    private HashMap<Integer, Integer> map = new HashMap<>();
    private int target;

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null)
            return 0;

        map.put(0, 1);
        target = targetSum;
        preOrder(root);

        map = null;
        root = null;
        System.gc();

        return res;
    }

    private void preOrder(TreeNode root) {
        /*计算累加路径*/
        sum += root.val;
        res += map.getOrDefault(sum - target, 0);
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        /*先序遍历*/
        if (root.left != null)
            preOrder(root.left);
        if (root.right != null)
            preOrder(root.right);
        /*回溯*/
        map.put(sum, map.get(sum) - 1);
        sum -= root.val;
    }

    /**
     * 第一次 迭代解决 前序遍历的较为复杂的问题
     *
     * @param root      树的根节点
     * @param targetSum 所找累加和
     * @return 累加和在树路径上的出现次数
     */
    public int pathSumIteration(TreeNode root, int targetSum) {
        if (root == null)
            return 0;

        int sum = 0, res = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        LinkedList<TreeNode> stack = new LinkedList<>();

        sum += root.val;
        stack.push(root);
        map.put(0, 1);
        map.put(root.val, root.val == 0 ? 2 : 1);
        if (root.val == targetSum)
            res++;

        while (root != null) {
            if (root.left != null) {
                TreeNode left = root.left;
                root.left = null;
                root = left;
                stack.push(root);
                //————— attach —————————————————————————————————
                sum += root.val;
                res += map.getOrDefault(sum - targetSum, 0);
                map.put(sum, map.getOrDefault(sum, 0) + 1);
                //————— attach —————————————————————————————————
                continue;
            }
            if (root.right != null) {
                TreeNode right = root.right;
                root.right = null;
                root = right;
                stack.push(root);
                //————— attach —————————————————————————————————
                sum += root.val;
                res += map.getOrDefault(sum - targetSum, 0);
                map.put(sum, map.getOrDefault(sum, 0) + 1);
                //————— attach —————————————————————————————————
                continue;
            }

            if (stack.isEmpty())
                return res;

            //————— attach — 回溯 ————————————————————————————————
            map.put(sum, map.get(sum) - 1);
            sum -= root.val;
            //————— attach —————————————————————————————————
            stack.pop();
            root = stack.peek();
        }

        return res;
    }
}
